package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import java.util.*

/*
https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/
https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html#_111-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E6%B7%B1%E5%BA%A6

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
 */
class leetcode_111 {
    @Test
    fun test_1() {
        val n3 = TreeNode(3)
        val n9 = TreeNode(9)
        val n20 = TreeNode(20)
        val n15 = TreeNode(15)
        val n7 = TreeNode(7)
        n3.left = n9
        n3.right = n20
        n20.left = n15
        n20.right = n7

        val actual = minDepth(n3)
        val expected = 2
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_2() {
        val root = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val n6 = TreeNode(6)
        root.right = n3
        n3.right = n4
        n4.right = n5
        n5.right = n6

        val actual = minDepth(root)
        val expected = 5
        Assert.assertEquals(expected, actual)
    }

    private fun minDepth(root: TreeNode?): Int {
        return minDepth1(root)
//        return minDepth2(root)
//        return minDepth3(root)
    }

    private fun minDepth1(root: TreeNode?): Int {
        // 广度遍历
        // S - N
        // T - N
        // 只有当左右孩子都为空的时候，才说明遍历的最低点了。
        if (null == root) {
            return 0
        }

        val queue: LinkedList<TreeNode> = LinkedList<TreeNode>()
        var deepth: Int = 0
        queue.offer(root)

        while (!queue.isEmpty()) {
            var size = queue.size
            deepth++
            while (size-- > 0) {
                val node = queue.poll()
                if (node.left == null && node.right == null) {
                    return deepth
                }
                node.left?.let { queue.offer(it) }
                node.right?.let { queue.offer(it) }
            }
        }
        return deepth
    }

    private fun minDepth2(root: TreeNode?): Int {
        /**
        1 后序遍历
        2 思路：
        最小深度，默认为最大值
        当深度小于最小深度，则返回
         */
        // 深度遍历 - 后序遍历 ： 求高度，最小深度和最小高度是一样的
        // S - N
        // T - N
        if (null == root) {
            return 0
        }
        // 左
        val leftHeight = minDepth2(root.left)

        // 右
        val rightHieght = minDepth2(root.right)

        // 中
        if (null != root.left && null == root.right) {
            return leftHeight + 1
        }

        if (null == root.left && null != root.right) {
            return rightHieght + 1
        }
        val minChildHeight = Math.min(leftHeight, rightHieght)
        val minHeight = minChildHeight + 1
        return minHeight
    }


    private fun minDepth3(root: TreeNode?): Int {
        // 深度遍历 - 前序遍历,求 深度
        // S - N
        // T - N
        if (null == root) {
            return 0
        }
        getDepth(root, 1)
        return minDepth
    }

    var minDepth: Int = Int.MAX_VALUE
    private fun getDepth(root: TreeNode?, currentDepth: Int) {
        if (null == root) {
            return
        }
        // 中 左 右

        // 中
//        if (null == root.left && null == root.right) {
//            minDepth = Math.min(minDepth, currentDepth)
//            // TODO:找到第一个就是最小的
//            // return
//        }
//        var depth: Int = currentDepth
//        // 左
//        if (null != root.left) {
//            depth++
//            getDepth(root.left, depth)
//            depth--
//        }
//        // 右
//        if (null != root.right) {
//            depth++
//            getDepth(root.right, depth)
//            depth--
//        }

        if (null == root.left && null == root.right) {
            minDepth = Math.min(minDepth, currentDepth)
             return
        }
        // 左
        if (null != root.left) {
            getDepth(root.left, currentDepth+1)
        }
        // 右
        if (null != root.right) {
            getDepth(root.right, currentDepth+1)
        }
    }
}